package com.salim.leetcode.$173;

import javax.swing.tree.TreeNode;
import java.util.Stack;

public class BSTIterator {
    //这题还有一种做法把节点放数组里 next o(1) 空间 o(n)

    //将左节点放入栈中 左节点即最小
    //next后pop一个 并从栈顶节点的右树中将左子节点放入栈中
    //栈不会超过树的高度 next方法似乎是o(1)的
    private Stack<TreeNode> stack;

    public BSTIterator(TreeNode root) {
        stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null) {
            stack.push(cur);
            if (cur.left != null)
                cur = cur.left;
            else
                break;
        }
    }

    public boolean hasNext() {
        return !stack.isEmpty();
    }

    public int next() {
        TreeNode node = stack.pop();
        TreeNode cur = node;
        // traversal right branch
        if (cur.right != null) {
            cur = cur.right;
            while (cur != null) {
                stack.push(cur);
                if (cur.left != null)
                    cur = cur.left;
                else
                    break;
            }
        }
        return node.val;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
